package practise.alogrithm.hundredInterviewQuestions;

import practise.alogrithm.hundredInterviewQuestions.Utils.TreeBuilder;
import practise.alogrithm.hundredInterviewQuestions.Utils.TreeNode;
import practise.alogrithm.hundredInterviewQuestions.convertToConcurrent.*;
import sun.reflect.generics.tree.Tree;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * Created by angela on 6/8/2014.
 */
public class CopyComplexLinkedList {
    /**
     *
     * @param treeNode, use a tree node for the complex linked list
     */
    public static TreeNode copyComplexLinkedList(TreeNode treeNode){
        /*
        use the node address for the storage
        key is the original node, and the value is the new node
         */
        Map<TreeNode,TreeNode> treeNodeMap = new HashMap<>();
        /**
         * the key is the node in the orginal linked list, the value is the node linked to
         */
        Map<TreeNode,TreeNode> treeNodeLinks = new HashMap<>();

        TreeNode newLinkedList = new TreeNode();
        TreeNode tempNode = treeNode;
        TreeNode headOfNewLink = newLinkedList;
        /*
        first base on the right link
         */
        while(tempNode!=null){
            newLinkedList.setValue(tempNode.getValue());
            if(tempNode.getRight()!=null) {
                TreeNode nextNode = new TreeNode();

                newLinkedList.setRight(nextNode);
            }
            treeNodeMap.put(tempNode,newLinkedList);
            treeNodeLinks.put(tempNode,tempNode.getLeft());
            newLinkedList=newLinkedList.getRight();
            tempNode = tempNode.getRight();
        }

        Iterator<TreeNode> originalNodeIterator = treeNodeMap.keySet().iterator();
        while(originalNodeIterator.hasNext()){
            TreeNode originalNode = originalNodeIterator.next();
            TreeNode leftLinkNode = treeNodeLinks.get(originalNode);
            treeNodeMap.get(originalNode).setLeft(treeNodeMap.get(leftLinkNode));
        }

        return headOfNewLink;
    }

    public static void main(String[] args){
        TreeNode treeNode = TreeBuilder.buildTree();
        TreeNode result = ConvertTreeToBidirectionLink.convertTree(treeNode);

        while(result.getRight()!=null){
            System.out.print(result.getValue()+"==>");
            if(result.getRight()!=null)
                result=result.getRight();
        }

        System.out.println();
        while(result.getLeft()!=null){
            System.out.print(result.getValue()+"<==");
            result=result.getLeft();
        }
        System.out.println();
        result = copyComplexLinkedList(result);
        while(result.getRight()!=null){
            System.out.print(result.getValue()+"==>");
            if(result.getRight()!=null)
                result=result.getRight();
        }

        System.out.println();
        while(result.getLeft()!=null){
            System.out.print(result.getValue()+"<==");
            result=result.getLeft();
        }


    }
}
